Random numbers have applications in numerous areas including game playing, statistical sampling, evaluating integral equations, particle transport calculations, and computations in statistical physics, just to name a few. As a result, random number generators (“RNGs”) figure prominently in methods and systems that use random numbers. For example, RNGs are key components of secure systems and are used extensively to generate keys for cryptography. An ideal RNG generates numbers which cannot be predicted in advance and cannot be reliably reproduced. In other words, RNGs ideally generate a sequence of unbiased, random numbers. However, many commonly used RNGs either generate sequences of seemingly random numbers or may be susceptible to generating biased sequences of numbers.
RNGs have been implemented in software to generate sequences of seemingly random numbers using formulas and numerical methods. Software-based RNGs are in general formula-based RNGs and referred to as “pseudorandom number generators,” because the formulas allow for prediction and reproduction of a sequence of pseudorandom numbers, provided the same initial parameters are used. A recursive Lehmer pseudorandom number generator (“LPNG”) is an example of a commonly used pseudorandom number generator and is given by:xn+1=Axn+C(mod M)where                xn is the nth number of a sequence of random numbers; and        A, C, and M are parameters that can be adjusted to ensure that a sequence of numbers generated by the LPNG appears random.Typically, M is assigned the word size of a computer employed to compute a sequence of pseudorandom numbers, and x0, the seed, is assigned a prime number. For example, assigning A, C, and M the values 21, 1, and 32 (5 bits), respectively, and assigning x0 the prime number 13, the LPNG generates the following sequence of pseudorandom integers: 13, 18, 27, 24, 25, 14, 7, etc. Alternative approaches seed a pseudorandom number generator with the time produced by a computer-system clock each time the pseudorandom number generator is initiated. However, even using the time provided by a system clock is not infallible because one can determine the time when the pseudorandom number generator was initiated.        
Hardware-based RNGs have also been developed to generate sequences of random numbers from chaotic fluctuations observed in thermal noise generated by atomic, molecular, and electrical systems. For example, thermal noise is generated by an electric current flowing through an electrical conductor, which can be used as a source of a sequence of random numbers by associating numbers with the magnitude of voltage equilibrium fluctuations. The thermal noise occurs whether or not there is an applied voltage because of the random motion of electrons in the conductor. However, hardware-based RNGs are not always reliable sources of sequences of random numbers because the systems employed by the hardware-based RNGs are susceptible to environmental changes. For example, an electric noise-based RNG used to generate a sequence of random numbers can be biased by changing the temperature of the system. In addition, the methods typically employed to authenticate the randomness of the sequence generated by a hardware-based RNG are deterministic software-based methods, which can be used to determine whether the sequences are statistically well-behaved but cannot be used to evaluate the true randomness of the sequence.
Quantum random number generators (“QRNGs”) are another type of hardware-based RNG. QRNGs are based on quantum-mechanical properties of identical quantum systems. A sequence of random numbers can be generated by associating each number with the outcome of a measurement performed on a quantum system. The numbers generated in this manner are truly random because each measurement projects the state of a quantum system onto one of many possible states at the time the measurement is performed, and, according to the standard interpretation of quantum mechanics, no amount of refinement of the measurement methods and measuring devices can overcome the uncertainty in the outcome of a measurement performed on a quantum system. As a result, QRNGs are highly desirable systems for generating sequences of random numbers.
Quantum systems comprising just two discrete states, represented by “|0” and “|1,” can be used to implement QRNGs. Examples of two-state quantum systems include vertical and horizontal polarization states of an electromagnetic field, two energy states of an atomic system, and the two spin states of an electron or atomic nuclei. A quantum system with two discrete states is called a “qubit system,” and the states |0 and |1, called “qubit basis states,” can also be represented in set notation as {|0,|1}. A qubit system can exist in the state |0, the state |1, or in any of an infinite number of states that simultaneously comprise both |0 and |1. Any of the states that include both |0 and |1 can be represented mathematically as a linear superposition of states:|ψ=α|0+β|1The state |ψ is called a “qubit,” and the parameters α and β are complex-valued coefficients satisfying the condition:|α|2+|β|2=1When |0 and |1 are the two possible states determined by a measurement performed on the qubit system in the state |ψ, one has a probability |α|2 of finding the qubit system in the state |0 and a probability |β|2 of finding the qubit system in the state |1 One is said to be performing a measurement on the qubit system in the basis {|0,|1}.
The infinite number of states associated with a qubit system can be geometrically represented by a unit-radius, three-dimensional sphere called a “Bloch sphere”:
          ψ    〉    =                    cos        ⁡                  (                      θ            2                    )                    ⁢                      0        〉              +                  ⅇ                  ⅈ          ⁢                                          ⁢          ϕ                    ⁢              sin        ⁡                  (                      θ            2                    )                    ⁢                      1        〉            where                0≦θ<π, and        0≦φ<2π.FIG. 1 illustrates a Bloch sphere representation of a qubit system. As shown in FIG. 1, lines 101-103 are orthogonal x, y, and z Cartesian coordinate axes, respectively, and a Bloch sphere 106 is centered at the origin. There are an infinite number of points on the Bloch sphere 106, each point representing a unique state of a qubit system. For example, a point 108 on the Bloch sphere 106 represents a unique state of a qubit system that simultaneously comprises, in part, the state |0 and, in part, the state |1. However, once the state of the qubit system is measured in the basis {|0,|1}, the state of the qubit system is projected onto the state |0 110 or onto the state |1 112.        
FIG. 2 illustrates a hypothetical single polarizing beamsplitter-based QRNG 200. The QRNG 200 comprises a polarizing beamsplitter 202, two photon detectors 204 and 206, and a photon source 208. The beamsplitter 202 comprises a multilayer dielectric thin film 210 sandwiched between two prisms 212 and 214. The beamsplitter 202 has an input channel 216 and two output channels 218 and 220. The channels 216, 218, and 220 represent either optical fibers or free space. The beamsplitter 202 reflects vertically polarized electromagnetic radiation and transmits horizontally polarized electromagnetic radiation. The beamsplitter 202 and photon source 208 can be used to generate a random number as follows. When the photon source 208 outputs a single photon of electromagnetic radiation polarized at 45° to the plane of the beamsplitter 202, the associated coherent linear superposition of states is given by:
                45      ⁢      °        〉    =                    1                  2                    ⁢                      V        〉              +                  1                  2                    ⁢                      H        〉            where                |V represents a vertical polarization state of the photon; and        |H represents a horizontal polarization state of the photon.The vertical and horizontal polarization states, |V and |H, are orthogonal basis states of the single photon polarized at 45° and observing the polarization states |V and |H can be associated with the binary numbers “1” and “0,” respectively. The photon remains in the state |45° until the photon is detected at either the photon detector D1 204 or the photon detector D2 206. The square of the coefficients of the state |45° indicates that there is a 1/2 probability of detecting the photon |V at the detector D1 204 and a 1/2 probability of detecting the photon |H at the detector D2 206. In other words, detecting a photon at the detector 204 can be associated with generating the binary value “1,” and detecting a photon at the detector 206 can be associated with generating the binary value “0.” Because the probability of detecting either polarization state is 1/2, generating the binary value “0” or “1” is a truly random event.        
The QRNG 200 can be used to generate a sequence of random binary numbers which can be partitioned into a sequence of random n-bit words. The sequence of random n-bit words can then be used in a variety of random-number applications. For example, the QRNG 200 can be used to generate a sequence of random integers between 0 and 31 as follows. When a photon |H is detected by the detector D2 206, the binary number “0” is added to a sequence of binary numbers, and when a photon |V is detected by the detector D1 204, the binary number “1” is added to the same sequence of binary numbers. Suppose that generating the state |45° 30 times consecutively generates the following sequence of random binary numbers:                000110101011100101010111100100The sequence of random binary numbers can be partitioned into 5-bit words to give a random sequence of base 2 numbers 00011, 01010, 11100, 10101, 01111, and 00100, which can then be translated into a corresponding sequence of random base 10 integers 3, 10, 28, 21, 15, and 4, respectively.        
Although the QRNG 200 appears to offer a convenient method and system for generating a sequence of random numbers, the QRNG 200 may be susceptible to generating sequences of pseudorandom numbers by tampering with the photon source 208. For example, an adversary that acquires control of the photon source 208 can bias the photon source 208 so that the coherent linear superposition of photons output by the photon source 208 are represented by the state:
          χ    〉    =                    1                  3                    ⁢                      V        〉              +                            2          3                    ⁢                      H        〉            As a result, the QRNG 200 generates a biased sequence of binary numbers where approximately ⅔ of the binary numbers generated equal “0” and approximately ⅓ of the binary numbers generated equal “1.” Moreover, the methods typically employed to authenticate the randomness of a sequence generated by a device, such as the QRNG 200, are often deterministic software-based methods, which are unreliable for determining whether or not a sequence of binary numbers is truly random. Physicists, cryptographers, computer scientists, and quantum-information users have recognized a need for QRNGs that can be used to reliably generate sequences of random numbers, and can also detect, authenticate, and correct biases in the sequences of random numbers by QRNGs using methods that rely on the non-deterministic properties of quantum systems.